class Solution {
public:
    int integerBreak(int n) {
        vector<int>dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i <= n; i++)
        {
            for (int j = 1; j < i; j++)
            {
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));


            }







        }
        return dp[n];

    }
};

    class Solution {
    public:
        bool canPartition(vector<int>& nums) {
            int sum = 0;

            for (int i = 0; i < nums.size(); i++)
                sum += nums[i];
            if (sum % 2 == 1)return false;
            int target = sum / 2;
            vector<int>dp(10001, 0);

            dp[0] = 0;
            for (int i = 0; i < nums.size(); i++)
            {
                for (int j = target; j >= nums[i]; j--)
                {
                    dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
                }




            }
            if (dp[target] == target)return true;
            return false;










        }
};

    class Solution {
    public:
        int lastStoneWeightII(vector<int>& stones) {
            int sum = 0;
            for (int i = 0; i < stones.size(); i++)
                sum += stones[i];


            int target = sum / 2;
            vector<int>dp(1501, 0);

            dp[0] = 0;
            for (int i = 0; i < stones.size(); i++)
            {
                for (int j = target; j >= stones[i]; j--)
                {

                    dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);

                }



            }
            return sum - dp[target] - dp[target];
















        }
};

    class Solution {
    public:



        int findMaxForm(vector<string>& strs, int m, int n) {


            vector<vector<int>>dp(m + 1, vector<int>(n + 1, 0));
            //dp[i][j]=dp[i-x][j-y]+1;
            dp[0][0] = 0;
            for (string str : strs)
            {
                int x = 0;
                int y = 0;
                for (char c : str)
                {
                    if (c == '0')x++;
                    if (c == '1')y++;
                }
                for (int i = m; i >= x; i--)
                {
                    for (int j = n; j >= y; j--)
                    {

                        dp[i][j] = max(dp[i - x][j - y] + 1, dp[i][j]);



                    }
                }







            }
            return dp[m][n];


        }
};

    class Solution {
    public:
        int change(int amount, vector<int>& coins) {

            vector<int>dp(amount + 1, 0);
            dp[0] = 1;
            for (int i = 0; i < coins.size(); i++)
            {
                for (int j = coins[i]; j <= amount; j++)
                {
                    dp[j] += dp[j - coins[i]];




                }
            }
            return dp[amount];



        }
};

    class Solution {
    public:
        int numSquares(int n) {
            int arr[] = { 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225,
                       256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900,
             961, 1024, 1089, 1156, 1225, 1296, 1369, 1444, 1521, 1600, 1681, 1764, 1849,
              1936, 2025, 2116, 2209, 2304, 2401, 2500, 2601, 2704, 2809, 2916, 3025, 3136,
              3249, 3364, 3481, 3600, 3721, 3844, 3969, 4096, 4225, 4356, 4489, 4624, 4761,
              4900, 5041, 5184, 5329, 5476, 5625, 5776, 5929, 6084, 6241, 6400, 6561, 6724,
              6889, 7056, 7225, 7396, 7569, 7744, 7921, 8100, 8281, 8464, 8649, 8836, 9025,
              9216, 9409, 9604, 9801, 10000 };
            vector<int>a(arr, arr + 100);


            vector<int>dp(n + 1, INT_MAX - 1);
            dp[0] = 0;
            //int cnt=strlen(arr);
            for (int i = 0; i < a.size(); i++)
            {
                for (int j = a[i]; j <= n; j++)
                {


                    dp[j] = min(dp[j], dp[j - a[i]] + 1);


                }





            }
            return dp[n];


        }
};

    class Solution {
    public:
        bool wordBreak(string s, vector<string>& wordDict) {
            unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
            vector<bool>dp(s.size() + 1, false);
            dp[0] = true;
            for (int i = 1; i <= s.size(); i++)
            {
                for (int j = 0; j < i; j++)
                {
                    string word = s.substr(j, i - j);
                    if (wordSet.find(word) != wordSet.end() && dp[j])
                        dp[i] = true;





                }
            }







            return dp[s.size()];

        }
};

    class Solution {
    public:
        int rob(vector<int>& nums) {
            vector<int>dp(nums.size() + 1);
            if (nums.size() == 0)return 0;
            if (nums.size() == 1)return nums[0];
            dp[0] = nums[0];
            dp[1] = max(nums[0], nums[1]);

            for (int i = 2; i < nums.size(); i++)
            {
                dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);



            }
            return dp[nums.size() - 1];










        }
};

    class Solution {
    public:
        int rb1(vector<int>& nums) {
            vector<int>dp(nums.size() + 1);
            if (nums.size() == 0)return 0;
            if (nums.size() == 1)return nums[0];
            dp[0] = nums[0];
            dp[1] = max(nums[0], nums[1]);

            for (int i = 2; i < nums.size(); i++)
            {
                dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
            }
            return dp[nums.size() - 1];
        }
        int rob(vector<int>& nums) {
            vector<int>new1(nums.begin(), nums.end() - 1);
            vector<int>new2(nums.begin() + 1, nums.end());
            int ret1 = rb1(new1);
            int ret2 = rb1(new2);
            if (nums.size() == 1)return nums[0];
            return max(ret1, ret2);


        }
};

    class Solution {
    public:
        vector<int> rob1(TreeNode* cur)
        {
            if (cur == nullptr)
                return vector<int>{0, 0};
            vector<int> dpleft = rob1(cur->left);
            vector<int> dpright = rob1(cur->right);
            int val1 = cur->val + dpleft[0] + dpright[0];
            int val2 = max(dpleft[0], dpleft[1]) + max(dpright[0], dpright[1]);
            return { val2,val1 };







        }




        int rob(TreeNode* root) {
            vector<int>dp = rob1(root);
            return max(dp[0], dp[1]);


        }
};
```
